#include <stdlib.h>
#include "common.h"

void mergeSort(int array[], int n);

void mergeSort0(int array[], int *b, int low, int high);

void merge(int array[], int *b, int low, int mid, int high);

void main()
{
    int array[] = {6, 5, 4, 3, 2, 1};
    int len = 6;
    mergeSort(array, len);
    print(array, len);
}

void mergeSort(int array[], int n)
{
    int *b = (int *)malloc(n * sizeof(int));
    mergeSort0(array, b, 0, n - 1);
}

void mergeSort0(int array[], int *b, int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        mergeSort0(array, b, low, mid);
        mergeSort0(array, b, mid + 1, high);
        merge(array, b, low, mid, high);
    }
}

void merge(int array[], int *b, int low, int mid, int high)
{
    int i, j, k;
    for (k = low; k <= high; k++)
    {
        b[k] = array[k];
    }

    for (i = low, j = mid + 1, k = i; i < mid + 1 && j <= high; k++)
    {
        if (b[i] <= b[j])
        {
            array[k] = b[i++];
        }
        else
        {
            array[k] = b[j++];
        }
    }

    while (i <= mid) array[k++] = b[i++];
    while (j <= high) array[k++] = b[j++];
}